The construction of minimal deterministic finite state automata (FSA) corresponding to regular expressions is an operation of very significant importance in a wide range of applications of computer science, including network firewalls, virus protection, natural language processing and biological computing amongst others.
The classical process of translation of regular expressions is a multi-step process, consisting of:    1. construction of a non-deterministic FSA corresponding to the regular expression;    2. determinisation of the automaton;    3. minimization of the obtained deterministic FSA.
The process is complex. Its space requirements are usually rather large due to the size of the constructed non-minimal deterministic FSA at Step 2. It also requires that the automaton be completely rebuilt to accommodate every modification of the source regular expression.